package leetcode_core.leetcode_1;

import org.junit.Test;

public class NumWays {

    public int numWays(int n) {
        if(n==1 || n==0){
            return 1;
        }
        if(n==2){
            return 2;
        }
        //1.定义dp数组
        //1.1 首先确定状态,状态就是会变化的东西,那么在本题中就是青蛙所在的阶数,是一维的,因此使用一维即可
        //    通过状态确定最终状态,dp[i]代表从第0阶到第i阶共有几种跳法,因此最终要求的就是dp[n]
        //1.2 确定选择,选择就是这次是选择跳一步?还是选择跳两步?
        //1.3 确定base-case,当台阶数=0的时候,这时候只需要跳法有且只有1种
        //     当台阶数为1的时候,也是只有一种,当台阶数为2的时候,有两种 1(两次都跳1)+1(跳一次跳2)
        //1.4 确定遍历方向:顺序遍历
        //1.5 状态转移方程:dp[i] = dp[i-1]+dp[i-2]:i-1表示跳一格,i-2表示跳两格,由于题目要求的是所有的次数,因此用加法
        int[] dp = new int[n+1];
        dp[0]=1;dp[1]=1;dp[2]=2;
        for(int i =3;i<=n;i++){
            dp[i] = (dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }

    @Test
    public void test(){
        System.out.println(numWays(2));
        System.out.println(numWays(7));
        System.out.println(numWays(0));
    }

}
